{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Time to Collect All Apples in a Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #收集树上所有苹果的最少时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵有&nbsp;<code>n</code>&nbsp;个节点的无向树，节点编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n-1</code>&nbsp;，它们中有一些节点有苹果。通过树上的一条边，需要花费 1 秒钟。你从&nbsp;<strong>节点 0&nbsp;</strong>出发，请你返回最少需要多少秒，可以收集到所有苹果，并回到节点 0 。</p>\n",
    "\n",
    "<p>无向树的边由&nbsp;<code>edges</code>&nbsp;给出，其中&nbsp;<code>edges[i] = [from<sub>i</sub>, to<sub>i</sub>]</code>&nbsp;，表示有一条边连接&nbsp;<code>from</code>&nbsp;和&nbsp;<code>to<sub>i</sub></code> 。除此以外，还有一个布尔数组&nbsp;<code>hasApple</code> ，其中&nbsp;<code>hasApple[i] = true</code>&nbsp;代表节点&nbsp;<code>i</code>&nbsp;有一个苹果，否则，节点&nbsp;<code>i</code>&nbsp;没有苹果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/05/10/min_time_collect_apple_1.png\" style=\"height: 212px; width: 300px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]\n",
    "<strong>输出：</strong>8 \n",
    "<strong>解释：</strong>上图展示了给定的树，其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/05/10/min_time_collect_apple_2.png\" style=\"height: 212px; width: 300px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>上图展示了给定的树，其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10^5</code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>&nbsp;&lt; b<sub>i</sub>&nbsp;&lt;= n - 1</code></li>\n",
    "\t<li><code>hasApple.length == n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-time-to-collect-all-apples-in-a-tree](https://leetcode.cn/problems/minimum-time-to-collect-all-apples-in-a-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-time-to-collect-all-apples-in-a-tree](https://leetcode.cn/problems/minimum-time-to-collect-all-apples-in-a-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7\\n[[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]]\\n[false,false,true,false,true,true,false]', '7\\n[[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]]\\n[false,false,true,false,false,true,false]', '7\\n[[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]]\\n[false,false,false,false,false,false,false]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        def dfs(cur, p):\n",
    "            if len(G[cur]) == 1 and p!=-1:\n",
    "                return hasApple[cur] * 2\n",
    "            ans = sum(dfs(nei, cur) for nei in G[cur] if nei != p)\n",
    "            return ans if ans == 0 and not hasApple[cur] else ans + 2\n",
    "        G = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            G[x], G[y] = G[x] + [y], G[y] + [x]\n",
    "        return max(0, dfs(0, -1) - 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    #node：开始迭代的节点的索引，最开始是根节点，接着是根节点的孩子\n",
    "    #parent：一开始为空（任意一个不可行值都可以），因为最少有一个节点，所以排除了空树的情况\n",
    "    def dfs(self,node, parent, adj, hasApple):\n",
    "        totalTime, childTime= 0,0   #childTime 是直接子节点访问到苹果的时间\n",
    "        for child in adj[node]:\n",
    "            print(\"node: \"+str(node))\n",
    "            if child==parent: \n",
    "                print(child)\n",
    "                continue  \n",
    "            childTime=self.dfs(child, node, adj, hasApple);\n",
    "            if (childTime or hasApple[child]):\n",
    "                totalTime += childTime+2\n",
    "        return totalTime\n",
    "\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        adj = [[]*n for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            adj[x].append(y)    #确定每个节点的邻居都是谁，有孩子的节点\n",
    "            adj[y].append(x)    #确定每个节点的邻居都是谁，孩子的父母都是谁\n",
    "        print(adj)\n",
    "        return self.dfs(0, -1, adj, hasApple)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        def dfs(cur, p):\n",
    "            if len(G[cur]) == 1 and p!=-1:\n",
    "                return hasApple[cur] * 2\n",
    "            ans = sum(dfs(nei, cur) for nei in G[cur] if nei != p)\n",
    "            return ans if ans == 0 and not hasApple[cur] else ans + 2\n",
    "        G = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            G[x].append(y)\n",
    "            G[y].append(x)\n",
    "        return max(0, dfs(0, -1) - 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            tree[a].append(b)\n",
    "            tree[b].append(a)\n",
    "\n",
    "        ans = 0\n",
    "        def dfs(node, parent):\n",
    "            nonlocal ans\n",
    "            flag = hasApple[node]\n",
    "            for next in tree[node]:\n",
    "                if next != parent:\n",
    "                    flag |= dfs(next, node)\n",
    "            if flag:\n",
    "                ans += 2\n",
    "            return flag\n",
    "            \n",
    "        dfs(0, 0)\n",
    "        return max(0, ans - 2)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        def dfs(cur, p):\n",
    "            if len(G[cur]) == 1 and p!=-1:\n",
    "                return hasApple[cur] * 2\n",
    "            ans = 0\n",
    "            for nei in G[cur]:\n",
    "                if nei != p :\n",
    "                    ans += dfs(nei, cur)\n",
    "            print(cur, ans)\n",
    "            return ans if ans == 0 and not hasApple[cur] else ans + 2\n",
    "        G = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            G[x].append(y)\n",
    "            G[y].append(x)\n",
    "        return max(0, dfs(0, -1) - 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        vis = [False] * n \n",
    "        def dfs(node):\n",
    "            vis[node] = True\n",
    "            for ch in g[node]:\n",
    "                if not vis[ch]:\n",
    "                    dfs(ch)\n",
    "                # 这个染色只能从底向上染色，如果放在和上一句同级的话就会向下染色\n",
    "                    if hasApple[ch]:\n",
    "                        hasApple[node] = True \n",
    "\n",
    "        dfs(0)\n",
    "        res = 0\n",
    "        for x, y in edges:\n",
    "            if hasApple[x] and hasApple[y]:\n",
    "                res += 2\n",
    "        return res            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\r\n",
    "\r\n",
    "        def dfs(u, prev):\r\n",
    "            for v in u2v[u]:\r\n",
    "                if v == prev:\r\n",
    "                    continue\r\n",
    "                dfs(v, u)\r\n",
    "                if dp[v] != 0 or (dp[v] == 0 and hasApple[v]):\r\n",
    "                    dp[u] += dp[v] + 2\r\n",
    "\r\n",
    "        u2v = [[] for _ in range(n)]\r\n",
    "        for u, v in edges:\r\n",
    "            u2v[u].append(v)\r\n",
    "            u2v[v].append(u)\r\n",
    "        \r\n",
    "        # dp[i] 表示收集节点i为根子树中的苹果所需的最少时间.\r\n",
    "        dp = [0] * n\r\n",
    "        dfs(0, -1)\r\n",
    "        return dp[0]\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for f,t in edges:\n",
    "            graph[f].append(t)\n",
    "            graph[t].append(f)\n",
    "        fathers = list(range(n))\n",
    "        book = [0]*n\n",
    "        def dfs(node,father):\n",
    "            for son in graph[node]:\n",
    "                if(son != father and book[son] == 0):\n",
    "                    book[son] = 1\n",
    "                    fathers[son] = node\n",
    "                    dfs(son,node)\n",
    "            return \n",
    "        book[0] = 1\n",
    "        dfs(0,-1)\n",
    "        book = [0]*n\n",
    "        result = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(hasApple[i]):\n",
    "                fi = i\n",
    "                while(fi != 0 and book[fi] == 0):\n",
    "                    book[fi] = 1\n",
    "                    fi = fathers[fi]\n",
    "                    result += 2\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "\n",
    "        self.node_map = [[] for i in range(n)]\n",
    "        self.reverse_edges = [-1 for i in range(n)]\n",
    "        self.visited_node = [True if i == 0 else False for i in range(n)]\n",
    "        self.cost = 0\n",
    "\n",
    "        for edge in edges: # 这里先写入了每个节点的可能经过的节点（双向因为无向）\n",
    "            self.node_map[edge[0]].append(edge[1])\n",
    "            self.node_map[edge[1]].append(edge[0])\n",
    "\n",
    "        self.build_reverse_edges(0)\n",
    "\n",
    "        for i in range(n): # 从每个苹果出发往回dfs找路\n",
    "            if hasApple[i]:\n",
    "                self.dfs(i)\n",
    "\n",
    "        return self.cost * 2\n",
    "    \n",
    "    def build_reverse_edges(self, current_node): # 从根节点出发\n",
    "        for node in self.node_map[current_node]: # 遍历会从哪里来到当前节点\n",
    "            if node > 0 and self.reverse_edges[node] == -1: # 如果是非根节点（有父节点，也就是双向都通）并且还没有弄过反向路径，就弄一下\n",
    "                self.reverse_edges[node] = current_node\n",
    "                self.build_reverse_edges(node) # 然后向后迭代，直到到了最底部并且之前的节点已经都处理过了，这是我们就得到了一个「我的父节点是哪个节点」的反向路径\n",
    "    \n",
    "    def dfs(self, current_node):\n",
    "        if not self.visited_node[current_node]: # 有个中间态的map记录一下这个节点是不是来过了，因为可能是公共父节点，如果没来过就+1s（不是\n",
    "            self.visited_node[current_node] = True\n",
    "            self.cost += 1\n",
    "            self.dfs(self.reverse_edges[current_node])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for s, e in edges:\n",
    "            g[s].append(e)\n",
    "            g[e].append(s)\n",
    "\n",
    "        def dfs(idx, vis):\n",
    "            d, apple = 0, hasApple[idx]\n",
    "            for nx in g[idx]:\n",
    "                if nx in vis: continue\n",
    "                vis.add(nx)\n",
    "                r, a = dfs(nx, vis)\n",
    "                apple |= a\n",
    "                if a: d += r + 2\n",
    "            return d, apple\n",
    "\n",
    "        return dfs(0, set([0]))[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        tree=[[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            tree[a].append(b)\n",
    "            tree[b].append(a)\n",
    "        \n",
    "        visited=set()\n",
    "        def min_time(i):\n",
    "            if i in visited:\n",
    "                return False,0\n",
    "            visited.add(i)\n",
    "            count=0\n",
    "            for j in tree[i]:\n",
    "                if j not in visited:\n",
    "                    has_apple,t=min_time(j)\n",
    "                    if has_apple:\n",
    "                        count+=2+t\n",
    "            has_apple=count>0 or hasApple[i]\n",
    "            return has_apple,count\n",
    "        \n",
    "        _,t=min_time(0)\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        edge_matrix = [[] * n for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            edge_matrix[edge[0]].append(edge[1])\n",
    "            edge_matrix[edge[1]].append(edge[0])\n",
    "        self.edge_matrix = edge_matrix\n",
    "        self.hasApple = hasApple\n",
    "\n",
    "        self.path = []\n",
    "        self.path_set = set()\n",
    "        self.graph(0)\n",
    "        return 2 * len(self.path_set)\n",
    "        \n",
    "    def graph(self, i, pre=None):\n",
    "        self.path.append(i)\n",
    "        if self.hasApple[i]:\n",
    "            for j in range(len(self.path)-1, 0, -1):\n",
    "                if (self.path[j-1], self.path[j]) in self.path_set:\n",
    "                    break\n",
    "                self.path_set.add((self.path[j-1], self.path[j]))\n",
    "        for k in self.edge_matrix[i]:\n",
    "            if k == pre:\n",
    "                continue\n",
    "            self.graph(k, i)\n",
    "        self.path.pop()\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int: #邻接表+BFS 求每个节点的直系parent\n",
    "        parent = self.get_parent(n, edges)\n",
    "        res = 0\n",
    "        visited = set()\n",
    "        for i in range(n-1, -1, -1):    #从下往上遍历\n",
    "            if hasApple[i] == True:\n",
    "                if i == 0:              #也可以不要 因为下面的while也判断了\n",
    "                    continue            #只是细化把最简单的情况写出来  更明了\n",
    "                p = i\n",
    "                while p != 0 and p not in visited:\n",
    "                    visited.add(p)\n",
    "                    p = parent[p]\n",
    "                    res += 2\n",
    "        return res\n",
    "\n",
    "    def get_parent(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        parent = [0 for _ in range(n)]\n",
    "        adjvex = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            adjvex[x].append(y)\n",
    "            adjvex[y].append(x)\n",
    "        Q = [0]\n",
    "        visited = set()\n",
    "        visited.add(0)\n",
    "        while Q:\n",
    "            cur_len = len(Q)            #这道题可以不用 \n",
    "            for _ in range(cur_len):    #保证每次恰好遍历一层\n",
    "                cur = Q.pop(0)\n",
    "                for nxt in adjvex[cur]:\n",
    "                    if nxt not in visited:\n",
    "                        visited.add(nxt)\n",
    "                        parent[nxt] = cur\n",
    "                        Q.append(nxt)\n",
    "        return parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        # exception case\n",
    "        assert isinstance(n, int) and n >= 1\n",
    "        assert isinstance(edges, list) and len(edges) == n - 1\n",
    "        for edge in edges:\n",
    "            assert isinstance(edge, list) and len(edge) == 2\n",
    "        assert isinstance(hasApple, list) and len(hasApple) == n\n",
    "        # main method: (Union Find Set)\n",
    "        return self._minTime(n, edges, hasApple)\n",
    "\n",
    "    def _minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        assert isinstance(n, int) and n >= 1\n",
    "        assert isinstance(edges, list) and len(edges) == n - 1\n",
    "        for edge in edges:\n",
    "            assert isinstance(edge, list) and len(edge) == 2\n",
    "        assert isinstance(hasApple, list) and len(hasApple) == n\n",
    "\n",
    "        ufs_pa = [0 for _ in range(n)]  # parents\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            adj[x].append(y)\n",
    "            adj[y].append(x)\n",
    "\n",
    "        queue = [0]\n",
    "        visited = set()\n",
    "        visited.add(0)\n",
    "        while len(queue) > 0:\n",
    "            for _ in range(len(queue)):\n",
    "                cur_idx = queue.pop(0)\n",
    "                for next_idx in adj[cur_idx]:\n",
    "                    if next_idx not in visited:\n",
    "                        visited.add(next_idx)\n",
    "                        ufs_pa[next_idx] = cur_idx\n",
    "                        queue.append(next_idx)\n",
    "\n",
    "        res = 0\n",
    "        visited = set()\n",
    "        for idx in range(n - 1, -1, -1):\n",
    "            if hasApple[idx]:\n",
    "                if idx == 0:\n",
    "                    continue\n",
    "                pa = idx\n",
    "                while pa != 0 and pa not in visited:\n",
    "                    visited.add(pa)\n",
    "                    pa = ufs_pa[pa]\n",
    "                    res += 2\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        # 难题 dfs\n",
    "        # dfs的返回值表示以curr为根的子树中苹果的个数\n",
    "        def dfs(prev, curr):\n",
    "            nonlocal ans\n",
    "\n",
    "            # 如果是叶节点，那么子树里是否有苹果只用考虑自己\n",
    "            if len(graph[curr]) == 1:\n",
    "                # 如果有，说明这个节点必须来，那么(prev -> curr)这条边是必走的\n",
    "                ans += int(hasApple[curr])\n",
    "                return int(hasApple[curr])\n",
    "\n",
    "            # 如果是非叶节点，那么需要考虑自己，然后递归自己的每个子树\n",
    "            has = int(hasApple[curr])\n",
    "            for nxt in graph[curr]:\n",
    "                if nxt == prev:\n",
    "                    continue\n",
    "                has += dfs(curr, nxt)\n",
    "\n",
    "            # 如果有，说明这个节点必须来，那么(prev -> curr)这条边是必走的\n",
    "            if has:\n",
    "                ans += 1\n",
    "            \n",
    "            return has\n",
    "\n",
    "        # 特判只有一个根节点的树\n",
    "        if n == 1:\n",
    "            return 0\n",
    "\n",
    "        # 建图\n",
    "        # graph = {}\n",
    "        # for s,e in edges:\n",
    "        #     if s not in graph:\n",
    "        #         graph[s] = {e}\n",
    "        #     else:\n",
    "        #         graph[s].add(e)\n",
    "        #     if e not in graph:\n",
    "        #         graph[e] = {s}\n",
    "        #     else:\n",
    "        #         graph[e].add(s)\n",
    "        graph = defaultdict(list)\n",
    "        for s,e in edges:\n",
    "            graph[s].append(e)\n",
    "            graph[e].append(s)\n",
    "        ans = 0\n",
    "        for nxt in graph[0]:\n",
    "            dfs(0, nxt)\n",
    "        \n",
    "        # 每条边走两次\n",
    "        return ans * 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        adj = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            adj[u].append(v)\n",
    "            adj[v].append(u)\n",
    "        vis = [-1] * n\n",
    "        def dfs(i, k):\n",
    "            if vis[i] != -1:\n",
    "                return 0\n",
    "            vis[i] = k\n",
    "            ret = 0\n",
    "            for child in adj[i]:\n",
    "                cnt = dfs(child, k + 1)\n",
    "                if vis[child] > k and hasApple[child]:\n",
    "                    ret += cnt + 2\n",
    "                    hasApple[i] = True\n",
    "            return ret\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges, hasApple) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    " \n",
    "        def dfs(pre, node):\n",
    "            # visited.add(node)\n",
    "            time = 0\n",
    "            for nei in graph[node]:\n",
    "                if nei == pre:\n",
    "                    continue\n",
    "                child_time = dfs(node, nei) # time to collect all apples in the subtree\n",
    "                # when backtracking (similar to postorder, but on graph)\n",
    "                if child_time or hasApple[nei]:\n",
    "                    child_time += 2\n",
    "                time += child_time\n",
    "            return time\n",
    "        # visited = set()\n",
    "        return dfs(-1, 0)\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "https://www.tutorialcup.com/leetcode-solutions/minimum-time-to-collect-all-apples-in-a-tree-leetcode-solution.htm\n",
    "DFS, 统计为了采到所有苹果，需要走到的边，如果一条边需要走到，就一定要走两次，否则是无法回去的，最后的结果就是 要走到的边数 * 2\n",
    "\n",
    "DFS返回的结果就是，从这个点开始，要走到的边数，以及这个点需不需要走到，如果后面有苹果或者这个点有苹果，就是需要走到的\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = 0\n",
    "\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        graph = make_graph(edges, n)\n",
    "        #print(graph)\n",
    "        visited = set()\n",
    "        \n",
    "        def traverse(start):\n",
    "            visited.add(start)\n",
    "            for next_node in graph[start]:\n",
    "                if next_node not in visited:\n",
    "                    #print(start, next_node)\n",
    "                    traverse(next_node)\n",
    "                    if hasApple[next_node]:\n",
    "                        hasApple[start] = True\n",
    "\n",
    "        traverse(0)\n",
    "        #print(hasApple)\n",
    "        for f, t in edges:\n",
    "            if hasApple[f] and hasApple[t]:\n",
    "                self.result  += 1\n",
    "        return self.result * 2\n",
    "        \n",
    "\n",
    "def make_graph(edges, n):\n",
    "    graph = [[] for _ in range(n)]\n",
    "    #print(graph)\n",
    "    for f, t in edges:\n",
    "        #print(f, t)\n",
    "        graph[f].append(t)\n",
    "        graph[t].append(f)\n",
    "        #print(graph[f], graph[t])\n",
    "    return graph\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        f = [0] * n\n",
    "        has = hasApple[:]\n",
    "        g = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        def dfs(u, p):\n",
    "            for v in g[u]:\n",
    "                if v != p:\n",
    "                    dfs(v, u)\n",
    "                    if has[v]:\n",
    "                        f[u] += f[v] + 2\n",
    "            if has[u] or f[u]:\n",
    "                has[u] = True\n",
    "\n",
    "        dfs(0, -1)\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        root_tree = {idx: [] for idx in range(n)}\n",
    "        for (x, y) in edges:\n",
    "            root_tree[x].append(y)\n",
    "            root_tree[y].append(x)\n",
    "\n",
    "        def dfs(node, visited):\n",
    "            cnt = 2 if node and hasApple[node] else 0\n",
    "            for each in root_tree[node]:\n",
    "                if each not in visited:\n",
    "                    cnt += dfs(each, visited.union([each]))\n",
    "            if node and not hasApple[node] and cnt:\n",
    "                cnt += 2\n",
    "            return cnt\n",
    "\n",
    "        return dfs(0, set([0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        visited = set()\n",
    "        def dfs(node):\n",
    "            visited.add(node)\n",
    "            cost = 0\n",
    "            path = [node]\n",
    "            for nei in graph[node]:\n",
    "                if nei not in visited:\n",
    "                    c = dfs(nei)\n",
    "                    if c!=0 or hasApple[nei]:\n",
    "                        cost += c + 2\n",
    "            return cost\n",
    "        return max(0, dfs(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        # 构建图\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        visited = set()\n",
    "\n",
    "        # 判断根节点是否有苹果\n",
    "        def dfs(node):\n",
    "            visited.add(node)\n",
    "            if hasApple[node]: \n",
    "                return True\n",
    "            for nex in graph[node]:\n",
    "                if nex not in visited:\n",
    "                    if dfs(nex):\n",
    "                        hasApple[node] = True\n",
    "            return hasApple[node]\n",
    "\n",
    "        for node in range(n):   \n",
    "            dfs(node)\n",
    "        res=0\n",
    "        for u,v in edges:\n",
    "            if hasApple[u] and hasApple[v]:\n",
    "                res+=1\n",
    "        return res*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        hasApple[0] = False\n",
    "        if n == 1: return 0\n",
    "\n",
    "        e = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            e[a].append(b)\n",
    "            e[b].append(a)\n",
    "        \n",
    "        seen  = set([])\n",
    "        def dfs(node, prev):\n",
    "            if node in seen: return 0\n",
    "            seen.add(node)\n",
    "\n",
    "            res = sum(dfs(n, node) for n in e[node])\n",
    "            return res + 2 * (node != prev) if res > 0 else 2 * hasApple[node]\n",
    "        return dfs(0, 0)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        parent=self.get_parent(n,edges)\n",
    "        res=0\n",
    "        visited=set()\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if hasApple[i]==True:\n",
    "                if i==0:\n",
    "                    continue\n",
    "                p=i\n",
    "                while p!=0 and p not in visited:\n",
    "                    visited.add(p)\n",
    "                    p=parent[p]\n",
    "                    res+=2\n",
    "        return res\n",
    "    \n",
    "    def get_parent(self,n:int,edges:List[List[int]])->List[int]:\n",
    "        parent=[0 for _ in range(n)]\n",
    "        adjvex=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            adjvex[x].append(y)\n",
    "            adjvex[y].append(x)\n",
    "        Q=[0]\n",
    "        visited=set()\n",
    "        visited.add(0)\n",
    "        while Q:\n",
    "            cur_len=len(Q)\n",
    "            for _ in range(cur_len):\n",
    "                cur=Q.pop(0)\n",
    "                for nxt in adjvex[cur]:\n",
    "                    if nxt not in visited:\n",
    "                        visited.add(nxt)\n",
    "                        parent[nxt]=cur\n",
    "                        Q.append(nxt)\n",
    "        return parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        def dfs(u,f):\n",
    "            res = 0\n",
    "            for v in nxt[u]:\n",
    "                if v!=f:\n",
    "                    res += dfs(v, u)+2\n",
    "            return -2 if res==0 and not hasApple[u] else res\n",
    "        \n",
    "        nxt = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            nxt[u].append(v)\n",
    "            nxt[v].append(u)\n",
    "        return max(0, dfs(0, None))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        dic = collections.defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            dic[u].append(v)\n",
    "            dic[v].append(u)\n",
    "        visited = [False for _ in range(n)]\n",
    "        visited[0] = True\n",
    "\n",
    "        def dfs(root, visited):\n",
    "            res = 0\n",
    "            for child in dic[root]:\n",
    "                if not visited[child]:\n",
    "                    visited[child] = True\n",
    "                    tmp = dfs(child, visited)\n",
    "                    res += tmp\n",
    "                    if hasApple[child] or tmp:\n",
    "                        res += 2\n",
    "            return res\n",
    "\n",
    "        return dfs(0, visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        # build graph\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for e in edges:\n",
    "            f, t = e\n",
    "            graph[f].append(t)\n",
    "            graph[t].append(f)\n",
    "\n",
    "        # travese\n",
    "        self.path = {}\n",
    "        visited = [False] * n\n",
    "        self.traverse(graph, 0, [], hasApple, visited)\n",
    "\n",
    "        return len(self.path) * 2\n",
    "    \n",
    "    def traverse(self, graph, n, on_path, hasApple, visited):\n",
    "        if visited[n] == True:\n",
    "            return\n",
    "\n",
    "        if hasApple[n]:\n",
    "            for i in on_path:\n",
    "                self.path[i] = 1\n",
    "\n",
    "        visited[n] = True\n",
    "        for v in graph[n]:\n",
    "            on_path.append(str(n) + '+' + str(v))\n",
    "            self.traverse(graph, v, on_path, hasApple, visited)\n",
    "            on_path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int: \n",
    "\n",
    "        g=[[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        tree=[[] for _ in range(n)]\n",
    "        used=[False]*n\n",
    "        q=deque([0])\n",
    "       \n",
    "        while q:\n",
    "            node=q.popleft()\n",
    "            used[node]=True\n",
    "            tree[node]+=[i for i in g[node] if not used[i]]\n",
    "            if len(tree[node])>0:\n",
    "                for i in tree[node]:\n",
    "                    q.append(i)\n",
    "\n",
    "        def dfs(x:int)->int:\n",
    "\n",
    "            if len(tree[x])==0:\n",
    "                return hasApple[x]\n",
    "            x_len=0\n",
    "            for y in tree[x]:\n",
    "                y_len=dfs(y)\n",
    "                x_len+=y_len\n",
    "\n",
    "\n",
    "\n",
    "            return x_len if x_len==0 and not hasApple[x] else x_len+1\n",
    "\n",
    "\n",
    "        return max(dfs(0)*2-2,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        def dfs(pa, u):\n",
    "            cnt = 0\n",
    "            if hasApple[u]:\n",
    "                cnt += 1\n",
    "            tot = 0\n",
    "            for v in g[u]:\n",
    "                if v != pa:\n",
    "                    p, c = dfs(u, v)\n",
    "                    if c:\n",
    "                        tot += p + 2\n",
    "                        cnt += c\n",
    "                        # print(f'u={u}, v={v}, path={p}, cnt={c}, tot={tot}, cnt={cnt}')\n",
    "            return tot, cnt\n",
    "        return dfs(-1,0)[0]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\r\n",
    "from collections import defaultdict\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\r\n",
    "        visited = [False] * n\r\n",
    "\r\n",
    "        ed = defaultdict(list)\r\n",
    "\r\n",
    "        for start, end in edges:\r\n",
    "            ed[start].append(end)\r\n",
    "            ed[end].append(start)\r\n",
    "        \r\n",
    "        def dfs(node):\r\n",
    "            visited[node] = True\r\n",
    "            apple = hasApple[node]\r\n",
    "            dist = 0\r\n",
    "\r\n",
    "            for target in ed[node]:\r\n",
    "                if not visited[target]:\r\n",
    "                    a, d = dfs(target)\r\n",
    "                    if a:\r\n",
    "                        apple = True\r\n",
    "                        dist += d + 2\r\n",
    "\r\n",
    "            # print(node, apple, dist)\r\n",
    "            return apple, dist\r\n",
    "\r\n",
    "        return dfs(0)[1]\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        degree = [0] * n\n",
    "        mm = defaultdict(list)\n",
    "        for fr, to in edges:\n",
    "            degree[fr] += 1\n",
    "            degree[to] += 1\n",
    "            mm[fr].append(to)\n",
    "            mm[to].append(fr)\n",
    "        q = deque([i for i in range(1, n) if degree[i] == 1 and not hasApple[i]])\n",
    "        # print(q)\n",
    "        while q:\n",
    "            p = q.popleft()\n",
    "            degree[p] -= 1\n",
    "            for nt in mm[p]:\n",
    "                degree[nt] -= 1\n",
    "                if degree[nt] == 1 and not hasApple[nt] and nt != 0:\n",
    "                    q.append(nt)\n",
    "        # print(degree)\n",
    "        ans = 0\n",
    "        visit = [False] * n\n",
    "        def in_order(x):\n",
    "            nonlocal ans, visit, mm\n",
    "            visit[x] = True\n",
    "            for nt in mm[x]:\n",
    "                if degree[nt] > 0 and not visit[nt]:\n",
    "                    ans += 1\n",
    "                    in_order(nt)\n",
    "                    ans += 1\n",
    "\n",
    "        in_order(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        ht, degree, ans = collections.defaultdict(list), [0] * n, n\n",
    "        for l, r in edges:\n",
    "            ht[l].append(r)\n",
    "            ht[r].append(l)\n",
    "            degree[l] += 1\n",
    "            degree[r] += 1\n",
    "        q = [i for i, v in enumerate(degree) if v == 1 and not hasApple[i] and i != 0]\n",
    "        while q:\n",
    "            ans -= 1\n",
    "            pop = q.pop()\n",
    "            for next in ht[pop]:\n",
    "                degree[next] -= 1\n",
    "                if degree[next] == 1 and not hasApple[next] and next != 0:\n",
    "                    q.append(next)\n",
    "                    degree[next] -= 1\n",
    "        \n",
    "        return max((ans-1) * 2, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int: \n",
    "\n",
    "        g=[[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        tree=[[] for _ in range(n)]\n",
    "        used=[False]*n\n",
    "        q=deque([0])\n",
    "       \n",
    "        while q:\n",
    "            node=q.popleft()\n",
    "            used[node]=True\n",
    "            tree[node]+=[i for i in g[node] if not used[i]]\n",
    "            if len(tree[node])>0:\n",
    "                for i in tree[node]:\n",
    "                    q.append(i)\n",
    "        print(tree)\n",
    "        # path=[0]*n\n",
    "        def dfs(x:int)->int:\n",
    "\n",
    "            print(x,'!!!')\n",
    "            if len(tree[x])==0:\n",
    "                return hasApple[x]\n",
    "            x_len=0\n",
    "            for y in tree[x]:\n",
    "                y_len=dfs(y)\n",
    "                print(x,y,\" @@@ \",x_len,' : ',y_len)\n",
    "                \n",
    "                x_len+=y_len\n",
    "\n",
    "            # path[x]=x_len\n",
    "\n",
    "            return x_len if x_len==0 and not hasApple[x] else x_len+1\n",
    "\n",
    "        ans=dfs(0)*2\n",
    "        # print(path)\n",
    "        return max(ans-2,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        # 除0之外，每个需要访问的节点都需要消耗2s; 每个节点若其子节点needVisit，则它也needVisit.\n",
    "\n",
    "        # 字典记录每个节点的前一个节点.\n",
    "        # BUG: 树无序，并不一定是前一个节点，需要确定0到每个节点的路径.\n",
    "\n",
    "        # TODO: 用一个map确定节点到0的路径.\n",
    "        to0_dict = dict()\n",
    "        to0_dict[0] = [0]\n",
    "\n",
    "        while True:\n",
    "            changed = False\n",
    "            for edge in edges:\n",
    "                if edge[0] in to0_dict and edge[1] not in to0_dict:\n",
    "                    to0_dict[edge[1]] = [edge[1]] + to0_dict[edge[0]]\n",
    "                    changed = True\n",
    "\n",
    "                elif edge[1] in to0_dict and edge[0] not in to0_dict:\n",
    "                    to0_dict[edge[0]] = [edge[0]] + to0_dict[edge[1]]\n",
    "                    changed = True\n",
    "\n",
    "            if not changed:\n",
    "                break\n",
    "\n",
    "        needVisit = [False] * n\n",
    "        for i in [idx for idx, boolean in enumerate(hasApple) if boolean]:\n",
    "            for x in to0_dict[i]:\n",
    "                needVisit[x] = True\n",
    "\n",
    "        result = len([x for x in needVisit[1:] if x]) * 2\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        myqueue = Queue()\n",
    "        myqueue.put(0)\n",
    "        child = [[] for i in range(n)]\n",
    "        parent = [False for i in range(n)]\n",
    "        parent[0] = True\n",
    "        graph = [[] for i in range(n)]\n",
    "        for edge in edges:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "\n",
    "        while False in parent:\n",
    "            i = myqueue.get()\n",
    "            for j in graph[i]:\n",
    "                if parent[j] == False:\n",
    "                    myqueue.put(j)\n",
    "                    child[i].append(j)\n",
    "                    parent[j] = True\n",
    "        # for i in range(n):\n",
    "           \n",
    "        #     for edge in edges:\n",
    "        #         if (edge[0] == i and parent[edge[1]] == False):\n",
    "        #             child[i].append(edge[1])\n",
    "        #             parent[edge[1]] = True\n",
    "        #             #edges.remove(edge)\n",
    "        #         if (edge[1] == i and parent[edge[0]] == False):\n",
    "        #             child[i].append(edge[0])\n",
    "        #             parent[edge[0]] = True\n",
    "        #             #edges.remove(edge)\n",
    "\n",
    "        def get_time_i(num):\n",
    "            time = 0\n",
    "            have = hasApple[num]\n",
    "            if child[num] == []:\n",
    "               return 0,have\n",
    "            \n",
    "            \n",
    "            for i in child[num]:\n",
    "                timechild,ifapple = get_time_i(i)\n",
    "                if ifapple == True :\n",
    "                    time += timechild + 2\n",
    "                    have = True\n",
    "            return time,have\n",
    "        print(child)\n",
    "        timetot,has0  = get_time_i(0)\n",
    "        return timetot\n",
    "\n",
    "        \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, adjv, hasApple, root):\n",
    "        self.vis.add(root)\n",
    "        ans = 0\n",
    "        for child in adjv.get(root, []):\n",
    "            if child in self.vis:\n",
    "                continue\n",
    "            cnt_ans = self.dfs(adjv, hasApple, child)\n",
    "            if hasApple[child] or cnt_ans > 0:\n",
    "                ans += 2\n",
    "            ans += cnt_ans\n",
    "        # print('dfs({}) = {}'.format(root, ans))\n",
    "        return ans\n",
    "    \n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        adjv = {}\n",
    "        for s, e in edges:\n",
    "            adjv.setdefault(s, []).append(e)\n",
    "            adjv.setdefault(e, []).append(s)\n",
    "        \n",
    "        self.vis = set()\n",
    "        return self.dfs(adjv, hasApple, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 1: Recursive DFS + Graph Construction\n",
    "    time: O(n), space: O(n)\n",
    "    \"\"\"\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        adj = {i:[] for i in range(n)}\n",
    "        for par, child in edges:\n",
    "            adj[par].append(child)\n",
    "            adj[child].append(par)\n",
    "\n",
    "        def dfs(cur, par):\n",
    "            res = 0\n",
    "            \n",
    "            for child in adj[cur]:\n",
    "                if child == par:\n",
    "                    continue\n",
    "                child_res = dfs(child, cur)\n",
    "                if child_res or hasApple[child]:\n",
    "                    res += child_res + 2\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for i, j in edges:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(root):\n",
    "            visited.add(root)\n",
    "            for x in g[root]:\n",
    "                if x not in visited:\n",
    "                    dfs(x)\n",
    "                    if hasApple[x]:\n",
    "                        hasApple[root] = True       \n",
    "        dfs(0)\n",
    "        \n",
    "        res = 0\n",
    "        for i, j in edges:\n",
    "            if hasApple[i] and hasApple[j]:\n",
    "                res += 1\n",
    "        \n",
    "        return res * 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        ad=collections.defaultdict(list)\n",
    "        for s,e in edges:\n",
    "            ad[s].append(e)\n",
    "            ad[e].append(s)\n",
    "        vis=set()\n",
    "        def dfs(cur):\n",
    "            vis.add(cur)\n",
    "            for nex in ad[cur]:\n",
    "                if nex not in vis:\n",
    "                    dfs(nex)\n",
    "                    if hasApple[nex]==True:\n",
    "                        hasApple[cur]=True\n",
    "            return \n",
    "        dfs(0)\n",
    "        cnt=0\n",
    "        for s,e in edges:\n",
    "            if hasApple[e] and hasApple[e]:\n",
    "                cnt+=2\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        # 问题分析：所有的苹果都要被收集，然后求最优的方案，也就是说需要将所有有苹果的点的祖先找到\n",
    "        # 从一个有苹果的点，找到另外一个有苹果的点的路径\n",
    "        # 4和5的共同祖先是1，然后1和2的共同祖先是0，所以需要一层层的去找他们的共同祖先\n",
    "        # 一个祖先对应着4秒的路径消耗\n",
    "\n",
    "\n",
    "\n",
    "        # 建图\n",
    "        g = collections.defaultdict(list)\n",
    "        for p,c in edges:\n",
    "            g[p].append(c)\n",
    "            g[c].append(p)\n",
    "        # 思路中断了，dfs是遍历一次所有的节点，然后标记有苹果的节点的父节点为有苹果\n",
    "        vis = set()\n",
    "\n",
    "        def dfs(node):\n",
    "            vis.add(node)\n",
    "            # 找两个元素的祖先节点\n",
    "            for chi in g[node]:\n",
    "                if chi not in vis:\n",
    "                    dfs(chi)\n",
    "                    if hasApple[chi]:\n",
    "                        hasApple[node] = True\n",
    "        dfs(0)\n",
    "        ans = 0\n",
    "        for x,y in edges:\n",
    "            if hasApple[x] and hasApple[y]:\n",
    "                ans += 1\n",
    "        return ans * 2         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        # 将树中每个苹果的父节点都打上True这个flag，这样最后计算flag=true的个数*2即可\n",
    "        if n==1:\n",
    "            return 0\n",
    "            \n",
    "        tree_dict={}\n",
    "        for edge in edges:\n",
    "            k,v=edge\n",
    "            if k not in tree_dict:\n",
    "                tree_dict[k]=[v]\n",
    "            else:\n",
    "                tree_dict[k].append(v)\n",
    "            if v not in tree_dict:\n",
    "                tree_dict[v]=[k]\n",
    "            else:\n",
    "                tree_dict[v].append(k)\n",
    "        # 上面字典得到了每个节点的父节点集合和子节点集合\n",
    "        visited=set()\n",
    "        def dfs(root):\n",
    "            visited.add(root)\n",
    "            for node in tree_dict[root]:\n",
    "                if node not in visited:\n",
    "                    dfs(node)\n",
    "                    if hasApple[node]:\n",
    "                        hasApple[root]=True\n",
    "        dfs(0)\n",
    "        res=0\n",
    "        for k,v in edges:\n",
    "            if hasApple[k] and hasApple[v]:\n",
    "                res+=1\n",
    "        return res*2\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        map = {}\n",
    "        for e in edges:\n",
    "            if not e[0] in map:\n",
    "                map[e[0]] = [e[1]]\n",
    "            else:\n",
    "                map[e[0]].append(e[1])\n",
    "            \n",
    "            if not e[1] in map:\n",
    "                map[e[1]] = [e[0]]\n",
    "            else:\n",
    "                map[e[1]].append(e[0])\n",
    "        \n",
    "\n",
    "        def reverse_map(roots, parents, r_map):\n",
    "            if len(roots) == 0:\n",
    "                return\n",
    "            \n",
    "            n_roots = []\n",
    "            n_parents = []\n",
    "            for i in range(len(roots)):\n",
    "                root = roots[i]\n",
    "                parent = parents[i]\n",
    "                if root in map:\n",
    "                    children = [nd for nd in map[root] if nd != parent]\n",
    "                    n_roots.extend(children)\n",
    "                    n_parents.extend([root] * len(children))\n",
    "                    for c in children:\n",
    "                        r_map[c] = root\n",
    "            \n",
    "            reverse_map(n_roots, n_parents, r_map)\n",
    "\n",
    "\n",
    "        r_map = {}\n",
    "        reverse_map([0], [None], r_map)\n",
    "\n",
    "        apple_nodes = set([i for i in range(len(hasApple)) if hasApple[i]])\n",
    "\n",
    "        to_traverse = set()\n",
    "        for nd in apple_nodes:\n",
    "            root = nd\n",
    "            if root != 0:\n",
    "                to_traverse.add(root)\n",
    "            while root in r_map:\n",
    "                if r_map[root] == 0:\n",
    "                    break\n",
    "                to_traverse.add(r_map[root])\n",
    "                root = r_map[root]\n",
    "\n",
    "        return len(to_traverse) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        connections = collections.defaultdict(list)\n",
    "        edges = set([tuple(edge) for edge in edges])\n",
    "        parents = set([0])\n",
    "        while edges:\n",
    "            todiscard = []\n",
    "            for node1, node2 in edges:\n",
    "                if node1 in parents:\n",
    "                    connections[node1].append(node2)\n",
    "                    parents.add(node2)\n",
    "                    todiscard.append(tuple((node1, node2)))\n",
    "                elif node2 in parents:\n",
    "                    connections[node2].append(node1)\n",
    "                    parents.add(node1)\n",
    "                    todiscard.append(tuple((node1, node2)))\n",
    "            for discardEdge in todiscard:\n",
    "                edges.discard(discardEdge)\n",
    "        \n",
    "        def dfs(node):\n",
    "            children = []\n",
    "            for child in connections[node]:\n",
    "                children.append(dfs(child))\n",
    "            result = 0\n",
    "            for child in children:\n",
    "                if child[0]:\n",
    "                    result += child[1] + 2\n",
    "            return (any([child[0] for child in children]) or hasApple[node], result)\n",
    "\n",
    "        \n",
    "        return dfs(0)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        nodes = {i: [] for i in range(n)}\n",
    "        used = {i: 0 for i in range(n)}\n",
    "        for x, y in edges:\n",
    "            if used[y]:\n",
    "                nodes[y].append(x)\n",
    "            else:\n",
    "                nodes[x].append(y)\n",
    "            used[x] = used[y] = 1\n",
    "\n",
    "        def post_seac(root):\n",
    "            if not nodes[root]:\n",
    "                if hasApple[root]:\n",
    "                    return 0\n",
    "                return -1\n",
    "            child_list = []\n",
    "            for x in nodes[root]:\n",
    "                child_list.append(post_seac(x))\n",
    "            all_none = True\n",
    "            for i in range(len(child_list)):\n",
    "                if child_list[i] != -1:\n",
    "                    all_none = False\n",
    "                    child_list[i] += 2\n",
    "                else:\n",
    "                    child_list[i] = 0\n",
    "            if all_none:\n",
    "                if hasApple[root]:\n",
    "                    return 0\n",
    "                return -1\n",
    "            return sum(child_list)\n",
    "        \n",
    "        return max(post_seac(0), 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        nodes = {i: [] for i in range(n)}\n",
    "        used = {i: 0 for i in range(n)}\n",
    "        for x, y in edges:\n",
    "            if used[y]:\n",
    "                nodes[y].append(x)\n",
    "            else:\n",
    "                nodes[x].append(y)\n",
    "            used[x] = used[y] = 1\n",
    "\n",
    "        def post_seac(root):\n",
    "            if not nodes[root]:\n",
    "                if hasApple[root]:\n",
    "                    return 0\n",
    "                return -1\n",
    "            child_list = []\n",
    "            for x in nodes[root]:\n",
    "                child_list.append(post_seac(x))\n",
    "            all_none = True\n",
    "            for i in range(len(child_list)):\n",
    "                if child_list[i] != -1:\n",
    "                    all_none = False\n",
    "                    child_list[i] += 2\n",
    "                else:\n",
    "                    child_list[i] = 0\n",
    "            if all_none:\n",
    "                if hasApple[root]:\n",
    "                    return 0\n",
    "                return -1\n",
    "            return sum(child_list)\n",
    "        \n",
    "        return max(post_seac(0), 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        # todo 构建树的邻接表表示\n",
    "        graph = [set() for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "\n",
    "        def dfs(node):\n",
    "            # 叶子节点返回 0\n",
    "            if not graph[node]:\n",
    "                return 0\n",
    "\n",
    "            total_time = 0\n",
    "            for child in graph[node]:\n",
    "                # 删除子节点到当前节点的边，避免重复遍历\n",
    "                graph[child].remove(node)\n",
    "\n",
    "                # 递归遍历子节点\n",
    "                sub_time = dfs(child)\n",
    "\n",
    "                # 如果子节点有苹果或者子节点到叶子节点路径上有苹果，则路径上需要的时间为2\n",
    "                if sub_time > 0 or hasApple[child]:\n",
    "                    total_time += sub_time + 2\n",
    "            return total_time\n",
    "\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        tree = {}\n",
    "        visited = set()\n",
    "        for i in range(n):\n",
    "            tree[i] = []\n",
    "        for edge in edges:\n",
    "            tree[edge[0]].append(edge[1])\n",
    "            tree[edge[1]].append(edge[0])\n",
    "        \n",
    "        def collect(root):\n",
    "            if root in visited:\n",
    "                return -1\n",
    "            visited.add(root)\n",
    "            sum_ = 0\n",
    "            for child in tree[root]:\n",
    "                subTime = collect(child)\n",
    "                if subTime != -1:\n",
    "                    sum_ += subTime + 2\n",
    "            if sum_ > 0:\n",
    "                return sum_\n",
    "            elif sum_ == 0 and hasApple[root]:\n",
    "                return 0\n",
    "            else:\n",
    "                return -1\n",
    "        res = collect(0)\n",
    "        if res == -1:\n",
    "            return 0\n",
    "        else:\n",
    "            return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        graph = {}\n",
    "        def build():\n",
    "            for i in range(n):\n",
    "                graph[i] = graph.get(i, [])\n",
    "            for i in range(len(edges)):\n",
    "                f, t = edges[i]\n",
    "                graph[f].append(t)\n",
    "                graph[t].append(f)\n",
    "            \n",
    "        build()\n",
    "        visited = set()\n",
    "        def dfs(n):\n",
    "            if n in visited:\n",
    "                return 0\n",
    "            visited.add(n)\n",
    "            path = 0\n",
    "            for i in graph[n]:\n",
    "                path += dfs(i)\n",
    "            \n",
    "            if (path > 0 or hasApple[n]) and n != 0:\n",
    "                path += 2\n",
    "            return path\n",
    "        return dfs(0)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        parent_dict = {}\n",
    "        neighbour_dict = defaultdict(list)\n",
    "        degree_dict = defaultdict(int)\n",
    "        for start, end in edges:\n",
    "            neighbour_dict[start].append(end)\n",
    "            neighbour_dict[end].append(start)\n",
    "        queue = deque([0])\n",
    "        white_leaf_list = []\n",
    "        visited = {0}\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            flag = True\n",
    "            for nxt in neighbour_dict[cur]:\n",
    "                if nxt not in visited:\n",
    "                    flag = False\n",
    "                    parent_dict[nxt] = cur\n",
    "                    degree_dict[cur] += 1\n",
    "                    visited.add(nxt)\n",
    "                    queue.append(nxt)\n",
    "            if flag and not hasApple[cur]:\n",
    "                white_leaf_list.append(cur)\n",
    "        queue = deque(white_leaf_list)\n",
    "        count = 0\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            if not cur:\n",
    "                break\n",
    "            count += 1\n",
    "            parent = parent_dict[cur]\n",
    "            degree_dict[parent] -= 1\n",
    "            if degree_dict[parent] == 0 and not hasApple[parent]:\n",
    "                queue.append(parent)\n",
    "        return 2 * (n - count - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "\n",
    "        if not any(hasApple):\n",
    "            return 0\n",
    "\n",
    "        tree = defaultdict(set)\n",
    "        for v1, v2 in edges:\n",
    "            tree[v1].add(v2)\n",
    "            tree[v2].add(v1)\n",
    "\n",
    "        node_set = set()\n",
    "\n",
    "        def search(node, father):\n",
    "            if hasApple[node]:\n",
    "                node_set.add(node)\n",
    "\n",
    "            for child in tree[node]:\n",
    "                if child != father:\n",
    "                    search(child, node)\n",
    "\n",
    "            if node in node_set:\n",
    "                node_set.add(father)\n",
    "\n",
    "        search(0, 0)\n",
    "\n",
    "        # print(tree)\n",
    "        # print(node_set)\n",
    "\n",
    "        cost = 0\n",
    "\n",
    "        def search1(node, father):\n",
    "            nonlocal cost\n",
    "\n",
    "            if node not in node_set:\n",
    "                return\n",
    "\n",
    "            cost += 1\n",
    "\n",
    "            # print(node, cost)\n",
    "\n",
    "            for child in tree[node]:\n",
    "                if child != father:\n",
    "                    search1(child, node)\n",
    "\n",
    "        search1(0, 0)\n",
    "\n",
    "        return 2*(cost - 1) if cost > 0 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(n, edges, hasApple):\n",
    "\n",
    "    edges_map = [set() for _ in range(n)]\n",
    "\n",
    "    for i, j in edges:\n",
    "        edges_map[i].add(j)\n",
    "        edges_map[j].add(i)\n",
    "\n",
    "\n",
    "    def dfs(i, seen):\n",
    "        nonlocal edges_map, hasApple\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        if i in seen:\n",
    "            return 0\n",
    "\n",
    "        seen.add(i)\n",
    "\n",
    "        for j in edges_map[i]:\n",
    "            if j in seen:\n",
    "                continue\n",
    "\n",
    "            x = dfs(j, seen)\n",
    "            if x > 0:\n",
    "                ret += x\n",
    "                ret += 2\n",
    "            elif hasApple[j]:\n",
    "                ret += 2\n",
    "\n",
    "        return ret\n",
    "\n",
    "    return dfs(0, set())\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        return f(n, edges, hasApple)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        graph = [set() for i in range(n)]\n",
    "        visited = set()\n",
    "        for v,u in edges:\n",
    "            graph[v].add(u)\n",
    "            graph[u].add(v)\n",
    "        \n",
    "        def dfs(root):\n",
    "            visited.add(root)\n",
    "            for node in graph[root]:\n",
    "                if node not in visited:\n",
    "                    dfs(node)\n",
    "                    if hasApple[node]:\n",
    "                         hasApple[root] = True\n",
    "        dfs(0)\n",
    "        #print(graph,hasApple)\n",
    "        res = 0\n",
    "        for u,v in edges:\n",
    "            if hasApple[u] and hasApple[v]:\n",
    "                res += 1\n",
    "        return res*2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        paths = defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            paths[a].add(b)\n",
    "            paths[b].add(a)\n",
    "        def dfs(i, p):\n",
    "            # print(\"def-start\", i)\n",
    "            a = 0\n",
    "            for j in paths[i]:\n",
    "                if j == p: continue\n",
    "                aj = dfs(j, i)\n",
    "                if aj:\n",
    "                    a += 2 if aj == 1 else 2 + aj\n",
    "            ans = 1 if a == 0 and hasApple[i] else a\n",
    "            # print(\"dfs\", i, ans)\n",
    "            return ans\n",
    "        ans = dfs(0, -1)\n",
    "        return 0 if ans == 1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        # dfs的返回值表示以curr为根的子树中苹果的个数\n",
    "        def dfs(prev, curr):\n",
    "            nonlocal ans\n",
    "\n",
    "            # 如果是叶节点，那么子树里是否有苹果只用考虑自己\n",
    "            if len(graph[curr]) == 1:\n",
    "                # 如果有，说明这个节点必须来，那么(prev -> curr)这条边是必走的\n",
    "                ans += int(hasApple[curr])\n",
    "                return int(hasApple[curr])\n",
    "\n",
    "            # 如果是非叶节点，那么需要考虑自己，然后递归自己的每个子树\n",
    "            has = int(hasApple[curr])\n",
    "            for nxt in graph[curr]:\n",
    "                if nxt == prev:\n",
    "                    continue\n",
    "                has += dfs(curr, nxt)\n",
    "\n",
    "            # 如果有，说明这个节点必须来，那么(prev -> curr)这条边是必走的\n",
    "            if has:\n",
    "                ans += 1\n",
    "            \n",
    "            return has\n",
    "\n",
    "        # 特判只有一个根节点的树\n",
    "        if n == 1:\n",
    "            return 0\n",
    "\n",
    "        # 建图\n",
    "        graph = {}\n",
    "        for s,e in edges:\n",
    "            if s not in graph:\n",
    "                graph[s] = {e}\n",
    "            else:\n",
    "                graph[s].add(e)\n",
    "            if e not in graph:\n",
    "                graph[e] = {s}\n",
    "            else:\n",
    "                graph[e].add(s)\n",
    "\n",
    "        ans = 0\n",
    "        for nxt in graph[0]:\n",
    "            dfs(0, nxt)\n",
    "        \n",
    "        # 每条边走两次\n",
    "        return ans * 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minTime(self, n, edges, hasApple):\n",
    "        p = [0] * n\n",
    "        d = collections.defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            d[u].add(v)\n",
    "            d[v].add(u)\n",
    "        p[0] = 1\n",
    "\n",
    "        def dfs(u):\n",
    "            ans = 0\n",
    "            for v in d[u]:\n",
    "                if not p[v]:\n",
    "                    p[v] = 1\n",
    "                    ans += dfs(v)\n",
    "            if ans or hasApple[u]:\n",
    "                return ans + 2\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        ans = dfs(0)\n",
    "        if ans:\n",
    "            return ans - 2\n",
    "        else:\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        parent = [-1] * n\n",
    "        parent[0] = -2\n",
    "        dic = collections.defaultdict(set)\n",
    "        for f,t in edges:\n",
    "            dic[f].add(t)\n",
    "            dic[t].add(f)\n",
    "        dq = collections.deque()\n",
    "        dq.append(0)\n",
    "        while dq:\n",
    "            f = dq.popleft()\n",
    "            for c in dic[f]:\n",
    "                if parent[c] == -1:\n",
    "                    parent[c] = f\n",
    "                    dq.append(c)\n",
    "        res = 0\n",
    "        for i, f in enumerate(hasApple):\n",
    "            if f:\n",
    "                cur = parent[i]\n",
    "                while cur >=0 and hasApple[cur] == False:\n",
    "                    hasApple[cur] = True\n",
    "                    cur = parent[cur]\n",
    "        if sum(hasApple) == 0:\n",
    "            return 0\n",
    "        return 2* (sum(hasApple)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 1443. 收集树上所有苹果的最少时间\n",
    "# 1. 随机遍历。因为是树，不是图，所以可以随机遍历，不用分DFS，BFS，遍历结果都是每个节点被遍历1次。\n",
    "# 2. 每当遇到苹果，就把当前节点和当前节点的所有祖先节点，都标记一下。具体的标记办法，是自底向上，遇到第一个已经标记过的节点则中止。\n",
    "# 3. 标记的所有节点的(数目-1)*2，就是最终答案。\n",
    "def make_graph(edges):\n",
    "    g = {}\n",
    "    for f, t in edges:\n",
    "        if f in g:\n",
    "            g[f].add(t)\n",
    "        else:\n",
    "            g[f] = {t}\n",
    "        if t in g:\n",
    "            g[t].add(f)\n",
    "        else:\n",
    "            g[t] = {f}\n",
    "    return g\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        g = make_graph(edges)\n",
    "        cand = {0: -1}\n",
    "        marked = {0}  # 一开始，只有起点是被标记的。\n",
    "        fathers = [-1] * n  # 一开始，不知到所有元素的父节点\n",
    "        while cand:\n",
    "            cur_node, father = cand.popitem()\n",
    "            # 如果当前点是苹果，就标记当前点以及所有祖先点。\n",
    "            if hasApple[cur_node] and cur_node not in marked:\n",
    "                marked.add(cur_node)\n",
    "                node = fathers[cur_node]\n",
    "                while node != -1 and node not in marked:\n",
    "                    marked.add(node)\n",
    "                    node = fathers[node]\n",
    "            # 把所有子节点加入候选集\n",
    "            for child in g[cur_node]:\n",
    "                if child != father:\n",
    "                    assert child not in cand\n",
    "                    cand[child] = cur_node\n",
    "                    fathers[child] = cur_node\n",
    "        return (len(marked) - 1) * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        parents = [-1]*n\n",
    "        graph = defaultdict(set)\n",
    "        for p,c in edges:\n",
    "            graph[p].add(c)\n",
    "            graph[c].add(p)\n",
    "        stack = [0]\n",
    "        while stack:\n",
    "            p = stack.pop()\n",
    "            for c in graph[p]:\n",
    "                if c!=0 and parents[c] == -1:\n",
    "                    parents[c] = p\n",
    "                    stack.append(c)\n",
    "        to_count_apples = [idx for idx,b in enumerate(hasApple) if b]\n",
    "        res = 0\n",
    "        while to_count_apples:\n",
    "            pop_apple = to_count_apples.pop()\n",
    "            parent_of_pop = parents[pop_apple]\n",
    "            if parent_of_pop == -1:\n",
    "                continue\n",
    "            if not hasApple[parent_of_pop]:\n",
    "                hasApple[parent_of_pop] = True\n",
    "                to_count_apples.append(parent_of_pop)\n",
    "            res += 2                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        son = {}\n",
    "        cnt = {}\n",
    "        \n",
    "        e = {}\n",
    "        for a, b in edges:\n",
    "            if a not in e:\n",
    "                e[a] = []\n",
    "            if b not in e:\n",
    "                e[b] = []\n",
    "            e[a].append(b)\n",
    "            e[b].append(a)\n",
    "        \n",
    "        def dfs(x):\n",
    "            son[x] = []\n",
    "            cnt[x] = 1 if hasApple[x] else 0\n",
    "            for y in e[x]:\n",
    "                if y in cnt:\n",
    "                    continue\n",
    "                son[x].append(y)\n",
    "                dfs(y)\n",
    "                cnt[x] += cnt[y]\n",
    "        \n",
    "        def walk(x):\n",
    "            ret = 0\n",
    "            for y in son[x]:\n",
    "                if cnt[y] > 0:\n",
    "                    ret += walk(y) + 2\n",
    "            return ret\n",
    "        \n",
    "        dfs(0)\n",
    "        return walk(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.children = []\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.tree = {}\n",
    "\n",
    "    def getStep(self, node, hasApple, parent):\n",
    "        res = 0\n",
    "        for child in node.children:\n",
    "            if child.val == parent:\n",
    "                continue\n",
    "            res += self.getStep(child, hasApple, node.val)\n",
    "        if res > 0 or hasApple[node.val]:\n",
    "            return res + 2\n",
    "        return 0\n",
    "\n",
    "\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        for i in range(n):\n",
    "            self.tree[i] = TreeNode(i)\n",
    "        for e in edges:\n",
    "            self.tree[e[0]].children.append(self.tree[e[1]])\n",
    "            self.tree[e[1]].children.append(self.tree[e[0]])\n",
    "        \n",
    "        return max(self.getStep(self.tree[0], hasApple, -1) - 2, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        web = [[] for _ in range(n)]\n",
    "\n",
    "        for u, v in edges:\n",
    "            web[u].append(v)\n",
    "            web[v].append(u)\n",
    "\n",
    "        def bfs():\n",
    "            vis, path = {0}, {0: \"\"}\n",
    "            q = deque([0])\n",
    "            count = set()\n",
    "\n",
    "            while q:\n",
    "                u = q.popleft()\n",
    "                if hasApple[u]:\n",
    "                    count.update(path[u].split())\n",
    "                for v in web[u]:\n",
    "                    if v not in vis:\n",
    "                        path[v] = path[u] + \" \" + str(v)\n",
    "                        q.append(v)\n",
    "                        vis.add(v)\n",
    "\n",
    "            return len(count) << 1\n",
    "        \n",
    "        return bfs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        @cache\n",
    "        def f(node, fa):\n",
    "            res, flag = 0, False\n",
    "            if hasApple[node]: flag = True\n",
    "            for nxt in g[node]:\n",
    "                if nxt != fa:\n",
    "                    a, b = f(nxt, node) \n",
    "                    if b:\n",
    "                        flag = True\n",
    "                        res += a + 2\n",
    "            return res, flag \n",
    "        \n",
    "        return f(0, -1)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        graph=collections.defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "        \n",
    "        visited=set()\n",
    "        def dfs(root):\n",
    "            visited.add(root)\n",
    "            for nex in graph[root]:\n",
    "                if nex not in visited:                    \n",
    "                    dfs(nex)\n",
    "                    if hasApple[nex]:\n",
    "                        hasApple[root]=True\n",
    "                        \n",
    "        dfs(0)\n",
    "        res=0\n",
    "        for u,v in edges:\n",
    "            if hasApple[u] and hasApple[v]:\n",
    "                res+=1\n",
    "\n",
    "        return res*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        # dfs\n",
    "        g = defaultdict(set)\n",
    "        for edge in edges:\n",
    "            x, y = edge\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        \n",
    "        visited = set()\n",
    "        def dfs(x):\n",
    "            has_app = hasApple[x]\n",
    "            for nxt in g[x]:\n",
    "                if nxt not in visited:\n",
    "                    visited.add(nxt)\n",
    "                    has_app |= dfs(nxt)\n",
    "            hasApple[x] = has_app\n",
    "            return has_app\n",
    "        \n",
    "        visited.add(0)\n",
    "        dfs(0)\n",
    "        ans = 0\n",
    "        for edge in edges:\n",
    "            x, y = edge\n",
    "            if hasApple[x] and hasApple[y]:\n",
    "                ans += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        d=defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            d[x].append(y)\n",
    "            d[y].append(x)\n",
    "        visited=[-1]*n\n",
    "        state=0\n",
    "        queue=[0]\n",
    "        while queue:\n",
    "            m=len(queue)\n",
    "            for i in range (0,m):\n",
    "                x=queue.pop(0)\n",
    "                visited[x]=state\n",
    "                for j in d[x]:\n",
    "                    if visited[j]==-1:\n",
    "                        queue.append(j)\n",
    "            state+=1\n",
    "        u=[[i,visited[i]] for i in range (0,n)]\n",
    "        u.sort(key=lambda x:-x[1])\n",
    "        y=[0]*n\n",
    "        dp=[0]*n\n",
    "        for i in range (0,n):\n",
    "            idx=u[i][0]\n",
    "            if hasApple[idx]:\n",
    "                y[idx]=1\n",
    "            else:\n",
    "                for j in d[idx]:\n",
    "                    if y[j]==1:\n",
    "                        y[idx]=1\n",
    "                        continue\n",
    "        for i in range (0,n):\n",
    "            idx=u[i][0]\n",
    "            if y[idx]==1:\n",
    "                dp[idx]=sum([dp[j] for j in d[idx]])+2*sum(y[j] for j in d[idx])\n",
    "        print(y)\n",
    "        return dp[0]//2\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        self.tree = {}\n",
    "        for e in edges:\n",
    "            if e[0] not in self.tree:\n",
    "                self.tree[e[0]] = {e[1]}\n",
    "            else:\n",
    "                self.tree[e[0]].add(e[1])\n",
    "            if e[1] not in self.tree:\n",
    "                self.tree[e[1]] = {e[0]}\n",
    "            else:\n",
    "                self.tree[e[1]].add(e[0])\n",
    "        print(self.tree)\n",
    "        self.ans = 0\n",
    "        if not self.tree: return 0\n",
    "        for i in self.tree[0]:\n",
    "            self.getApple(0,i,hasApple)\n",
    "        return self.ans *2\n",
    "    def getApple(self,last,curr,hasApple):\n",
    "        if len(self.tree[curr]) == 1:\n",
    "            # 如果有，说明这个节点必须来，那么(prev -> curr)这条边是必走的\n",
    "            self.ans += int(hasApple[curr])\n",
    "            return int(hasApple[curr])\n",
    "\n",
    "        # 如果是非叶节点，那么需要考虑自己，然后递归自己的每个子树\n",
    "        has = int(hasApple[curr])\n",
    "        for nxt in self.tree[curr]:\n",
    "            if nxt == last:\n",
    "                continue\n",
    "            has += self.getApple(curr, nxt,hasApple)\n",
    "        # 如果有，说明这个节点必须来，那么(prev -> curr)这条边是必走的\n",
    "        if has:\n",
    "            self.ans += 1\n",
    "        return has\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        nbs = defaultdict(set)\n",
    "        for e in edges:\n",
    "            nbs[e[0]].add(e[1])\n",
    "            nbs[e[1]].add(e[0])\n",
    "            \n",
    "        \n",
    "        def solve(i, fa):\n",
    "            res = []\n",
    "            for j in nbs[i]:\n",
    "                if j != fa:\n",
    "                    appled, twoway = solve(j, i)\n",
    "                    if appled:\n",
    "                        res.append(twoway)\n",
    "\n",
    "            if not res:\n",
    "                return hasApple[i], 0\n",
    "            return True, sum(x + 2 for x in res)\n",
    "\n",
    "        return solve(0, -1)[1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        graph=collections.defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "        \n",
    "        visited=set()\n",
    "        def dfs(root):\n",
    "            visited.add(root)\n",
    "            for nex in graph[root]:\n",
    "                if nex not in visited:                    \n",
    "                    dfs(nex)\n",
    "                    if hasApple[nex]:\n",
    "                        hasApple[root]=True\n",
    "        dfs(0)\n",
    "        numTrue = hasApple.count(True)\n",
    "        if numTrue == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return (numTrue-1) * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "\n",
    "        \n",
    "        self.sum = 0\n",
    "        self.savehash = {}\n",
    "        def makegraph(savehash,savehash2,position):\n",
    "            if savehash:\n",
    "                for i in savehash[position]:\n",
    "                    if i in savehash2:\n",
    "                        pass\n",
    "                    else:\n",
    "                        savehash2[i] = 0\n",
    "                        self.graph[position].append(i)\n",
    "                        savehash2 = makegraph(savehash,savehash2,i)\n",
    "                return savehash2\n",
    "            else:\n",
    "                return savehash2\n",
    "        \n",
    "        def fingpath(graph,position,savehash):\n",
    "            if graph[position]:\n",
    "                for i in graph[position]:\n",
    "                    self.sum += 1\n",
    "                    fingpath(graph,i,savehash)\n",
    "                    if savehash[i]:\n",
    "                        self.sum += 1\n",
    "                    else:\n",
    "                        self.sum -= 1\n",
    "            else:\n",
    "                pass\n",
    "            return\n",
    "        def makehash(graph,position):\n",
    "            if graph[position]:\n",
    "                for i in graph[position]:\n",
    "                    makehash(graph,i)\n",
    "                    if hasApple[position]:\n",
    "                        self.savehash[position] = True\n",
    "                    else:\n",
    "                        if position not in self.savehash or not self.savehash[position]:\n",
    "                            if self.savehash[i]:\n",
    "                                self.savehash[position] = True\n",
    "                            else:\n",
    "                                self.savehash[position] = False\n",
    "                        else:\n",
    "                            pass\n",
    "\n",
    "            else:\n",
    "                self.savehash[position] = hasApple[position]\n",
    "            return \n",
    "\n",
    "        savehash = {}\n",
    "        savehash2 = {0:0}\n",
    "        self.graph = [[] for i in range(n)]\n",
    "        for i in edges:\n",
    "            if i[0] in savehash:\n",
    "                savehash[i[0]].append(i[1])\n",
    "            else:\n",
    "                savehash[i[0]] = [i[1]]\n",
    "            if i[1] in savehash:\n",
    "                savehash[i[1]].append(i[0])\n",
    "            else:\n",
    "                savehash[i[1]] = [i[0]]\n",
    "        makegraph(savehash,savehash2,0)\n",
    "        makehash(self.graph,0)\n",
    "        fingpath(self.graph,0,self.savehash)\n",
    "        return self.sum\n",
    "        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def build_graph_set(edges):\n",
    "    import collections\n",
    "    graph = collections.defaultdict(set)\n",
    "    for edge in edges:\n",
    "        graph[edge[0]].add(edge[1])\n",
    "        graph[edge[1]].add(edge[0])\n",
    "    return graph\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        graph = build_graph_set(edges)\n",
    "\n",
    "        def dfs(node1, father=-1):\n",
    "            val = 0\n",
    "            for node2 in graph[node1]:\n",
    "                if node2 != father:\n",
    "                    val += dfs(node2, node1)\n",
    "\n",
    "            if val or hasApple[node1]:\n",
    "                return val + 2\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        return dfs(0) - 2 if dfs(0) else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        from collections import defaultdict\n",
    "        dic = defaultdict(set)\n",
    "        mustVisitNodes = set()\n",
    "        \n",
    "        for src, des in edges:\n",
    "            dic[src].add(des)\n",
    "            dic[des].add(src)\n",
    "            \n",
    "        def findMustVisitNodesDFS(node, path, visited):\n",
    "            path.append(node)\n",
    "            \n",
    "            if hasApple[node]:\n",
    "                for n in path:\n",
    "                    mustVisitNodes.add(n)\n",
    "            \n",
    "            for child in dic[node]:\n",
    "                if child not in visited:\n",
    "                    visited.add(child)\n",
    "                    findMustVisitNodesDFS(child, path + [node], visited)\n",
    "                \n",
    "        findMustVisitNodesDFS(0, [], set([0]))\n",
    "\n",
    "        return max(0, 2 * (len(mustVisitNodes) - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        # 特判只有一个节点的数\n",
    "        if n == 1:\n",
    "            return 0\n",
    "\n",
    "        # 建图\n",
    "        graph = {}\n",
    "        for s,e in edges:\n",
    "            if s not in graph:\n",
    "                graph[s] = {e}\n",
    "            else:\n",
    "                graph[s].add(e)\n",
    "            if e not in graph:\n",
    "                graph[e] = {s}\n",
    "            else:\n",
    "                graph[e].add(s)\n",
    "        \n",
    "        # 路径哈希去重\n",
    "        path_set = set()\n",
    "\n",
    "        # 统计苹果数量用于剪枝\n",
    "        apple_left = Counter(hasApple)[True]\n",
    "        \n",
    "        # 每个元素为：\n",
    "        # (现在在哪里，上一个是哪里，从0到现在位置的路径)\n",
    "        dq = deque([(0, None, [])])\n",
    "        while dq and apple_left:\n",
    "            curr, prev, path = dq.popleft()\n",
    "            for nxt in graph[curr]:\n",
    "                if nxt == prev:\n",
    "                    continue\n",
    "                if hasApple[nxt]:\n",
    "                    apple_left -= 1\n",
    "                    path_set.update(path)\n",
    "                    path_set.add((curr,nxt))\n",
    "                dq.append((nxt, curr, path + [(curr,nxt)]))\n",
    "\n",
    "        # 每条路径来回共走两遍\n",
    "        return len(path_set) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        link = collections.defaultdict(set)\n",
    "        for L,R in edges:\n",
    "            link[L].add(R)\n",
    "            link[R].add(L)\n",
    "        parent = collections.defaultdict(int)\n",
    "        BFS = [0]\n",
    "        for L in BFS:\n",
    "            for R in link[L]:\n",
    "                BFS.append(R)\n",
    "                link[R].remove(L)\n",
    "                parent[R] = L\n",
    "        ans = collections.defaultdict(int)\n",
    "        for R in BFS[:0:-1]:\n",
    "            if hasApple[R]:\n",
    "                ans[parent[R]] += 2 + ans[R]\n",
    "                hasApple[parent[R]]=True\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        graph = {}\n",
    "        for edge in edges:\n",
    "            p1,p2 = edge\n",
    "            if not p1 in graph:\n",
    "                graph[p1] = set()\n",
    "            if not p2 in graph:\n",
    "                graph[p2] = set()\n",
    "            graph[p1].add(p2)\n",
    "            graph[p2].add(p1)\n",
    "        guide = set()\n",
    "        for i in range(n):\n",
    "            if hasApple[i]:\n",
    "                guide.add(i)\n",
    "        visited = set()\n",
    "        visited.add(0)\n",
    "        def dfs(node):\n",
    "            s = 0\n",
    "            for next_nd in graph[node]:\n",
    "                if not next_nd in visited:\n",
    "                    visited.add(next_nd)\n",
    "                    s += dfs(next_nd)\n",
    "            if (s > 0 or node in guide ) and node != 0:\n",
    "                s += 2\n",
    "            # print(node,' ',s)\n",
    "            return s\n",
    "        return dfs(0)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 将无向图改成有向图\n",
    "    # 如果改结点有苹果或者，改结点的子结点含有苹果 -》一定会遍历一次改结点\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        \n",
    "        # 结点0是根节点\n",
    "        queue = collections.deque([0])\n",
    "        visited = set([0])\n",
    "        new_egdes = []\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for nxt in graph[node]:\n",
    "                if nxt not in visited:\n",
    "                    queue.append(nxt)\n",
    "                    visited.add(nxt)\n",
    "                    new_egdes.append([node, nxt])\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        for f, t in new_egdes:\n",
    "            graph[f].append(t)\n",
    "            \n",
    "        new_hasApple = collections.defaultdict(bool)\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(root = 0):\n",
    "            nonlocal new_hasApple\n",
    "            ans = hasApple[root] \n",
    "            for nxt in graph[root]:\n",
    "                ans |= dfs(nxt)\n",
    "            new_hasApple[root] = ans \n",
    "            return ans \n",
    "        \n",
    "        dfs()\n",
    "        return max((list(new_hasApple.values()).count(True) - 1) * 2, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        graph=collections.defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "        \n",
    "        visited=set()\n",
    "        def dfs(root):\n",
    "            visited.add(root)\n",
    "            for nex in graph[root]:\n",
    "                if nex not in visited:                    \n",
    "                    dfs(nex)\n",
    "                    if hasApple[nex]:\n",
    "                        hasApple[root]=True\n",
    "        dfs(0)\n",
    "        res=0\n",
    "        for u,v in edges:\n",
    "            if hasApple[u] and hasApple[v]:\n",
    "                res+=1\n",
    "        return res*2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        maps = {_:set() for _ in range(n)}\n",
    "        for edge in edges:\n",
    "            maps[edge[0]].add(edge[1])\n",
    "            maps[edge[1]].add(edge[0])\n",
    "        visited = [False for _ in range(n)]\n",
    "        def dfs(x,cost):\n",
    "            visited[x] = True\n",
    "            child_cost = 0\n",
    "            for child in maps[x]:\n",
    "                if visited[child]:\n",
    "                    continue\n",
    "                child_cost += dfs(child, 2)\n",
    "            if not child_cost and not hasApple[x]:\n",
    "                return 0\n",
    "            return cost + child_cost\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n",
    "        graph=collections.defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "        \n",
    "        visited=set()\n",
    "        def dfs(root):\n",
    "            visited.add(root)\n",
    "            for nex in graph[root]:\n",
    "                if nex not in visited:                    \n",
    "                    dfs(nex)\n",
    "                    if hasApple[nex]:\n",
    "                        hasApple[root]=True\n",
    "        dfs(0)\n",
    "        res=0\n",
    "        for u,v in edges:\n",
    "            if hasApple[u] and hasApple[v]:\n",
    "                res+=1\n",
    "        return res*2\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
